package com.gitee.feizns.explore.data_structure.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * 210. 课程表 II
 * @author feizns
 * @since 2020/2/27
 */
public class FindOrder {

    static int[][] p = new int[][]{ {0, 1}, {1, 0} };

    public static void main(String[] args) {
        System.out.println(Arrays.toString(findOrder(2, p)));
    }

    private static G graph;

    private static boolean[] visited;

    private static List<Integer> ret;

    private static Set<Integer> paths;

    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        paths = new HashSet<>();
        ret = new LinkedList<>();
        graph = new G(numCourses);
        for (int i = 0; i < prerequisites.length; i++)
            graph.addEdge(prerequisites[i][0], prerequisites[i][1]);
        visited = new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            paths.clear();
            if ( !dfs(i) )
                return new int[]{};
        }
        return ret();
    }

    private static boolean dfs(int k) {
        if ( paths.contains(k) )
            return false;
        if ( !visited[k] ) {
            paths.add(k);
            Set<Integer> adj = graph.adj(k);
            for (Integer v : adj)
                if ( !dfs(v) )
                    return false;
            visited[k] = true;
            ret.add(k);
            paths.remove(k);
        }
        return true;
    }

    private static int[] ret() {
        return ret.stream().mapToInt(Integer::intValue).toArray();
    }

    private static class G {
        Set<Integer>[] g;
        int[] in;
        public G(int size) {
            this.g = new Set[size];
            in = new int[size];
            for (int i = 0; i < g.length; i++)
                g[i] = new HashSet<>();
        }
        public Set<Integer> adj(int v) { return g[v]; }
        public void addEdge(int v, int t) {
            g[v].add(t);
            in[t]++;
        }
        public List<Set<Integer>> nodes() {
            return new ArrayList<>(Arrays.asList(g));
        }
        public int in(int v) {
            return in[v];
        }
    }

}
